#define _CRT_SECURE_NO_WARNINGS 1
//#include "test-5-19-task.h"

//int main(void)
//{
//	BTNode *Node1 = BinaryTreeCreate();
//	BinaryTreePrevOrder(Node1);
//	printf("\nBinaryTreeSize is %d", BinaryTreeSize(Node1));
//	printf("\nBinaryTreeLeafSize is %d", BinaryTreeLeafSize(Node1));
//	printf("\n");
//	BinaryTreeLevelOrder(Node1);
//	return 0;
//}

//int main()
//{
//	BTDataType* a = "ABD##E#H##CF##G##";
//	int i = 0;
//	BTNode* arr = prevorder(a, &i);
//	BinaryTreePrevOrder(arr);
//	return 0;
//}

#include <stdio.h>
#include <stdlib.h>

typedef struct Tree
{
    char val;
    struct Tree* left;
    struct Tree* right;
}BTNode;

BTNode* prevorder(char* a, int* i)
{
    if (a[*i] == '#')
    {
        (*i)++;
        return;
    }
    BTNode* ret = (BTNode*)malloc(sizeof(BTNode));
    ret->val = a[(*i)++];
    ret->left = prevorder(a, i);
    ret->right = prevorder(a, i);
    return ret;
}

void Inorder(BTNode* root)
{
    if (root == NULL)
        return;
    Inorder(root->left);
    printf("%c ", root->val);
    Inorder(root->right);
}

int main() {
    char* arr = { 0 };
    while (scanf("%s", arr) != EOF) 
    {
        int i = 0;
        BTNode* root = prevorder(arr, &i);
        prevorder(arr, &i);
        Inorder(root);
    }
    return 0;
}